package com.banana.linkedlist;

import org.junit.jupiter.api.Test;
import org.xml.sax.DTDHandler;
import sun.print.PSPrinterJob;

import javax.xml.soap.Node;
import java.lang.annotation.ElementType;
import java.util.Stack;

/**
 * 单链表实现108好汉的链式存储
 * 注意：单链表基础上的修改添加操作，应该在节点前判定break，因为只有在节点前，才能读取修改后面的节点
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList list = new SingleLinkedList();
        list.addByNo(hero1);
        list.addByNo(hero4);
        list.addByNo(hero3);
        list.addByNo(hero2);
        list.deleteNodeByNo(5);
        list.list();
        list.updateNode(new HeroNode(1,"武松","老虎杀手"));
        list.updateNode(new HeroNode(72,"武松","老虎杀手"));
        list.list();
    }

    @Test
    void testReverse() {
        // 测试
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList list = new SingleLinkedList();
        list.addByNo(hero1);
        list.addByNo(hero4);
        list.addByNo(hero3);
        list.addByNo(hero2);

        System.out.println("原先：");
        list.list();
        System.out.println("反转后：");
        SingleLinkedList.reverse(list.getHead());
        list.list();
    }

    @Test
    void testOrderGet() {
        // 测试
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList list = new SingleLinkedList();
        list.addByNo(hero1);
        list.addByNo(hero4);
        list.addByNo(hero3);
        list.addByNo(hero2);

        list.list();
        HeroNode lastOrder = list.getLastOrder(1);
        System.out.printf("倒数第%d个节点是" + lastOrder.toString(),1);
    }

    @Test
    void testPrintByOrder() {
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList list = new SingleLinkedList();
        list.addByNo(hero1);
        list.addByNo(hero4);
        list.addByNo(hero3);
        list.addByNo(hero2);
        SingleLinkedList.listByOrder(list.getHead());
        list.list();
    }
}

/**
 * 单链表
 */
class SingleLinkedList {
    private final HeroNode head = new HeroNode(0,"","");

    /**
     * 面试题1：反转一个链表
     * @return 链表
     */
    public static HeroNode reverse(HeroNode head) {
        // 1.头节点为null
        if (head.next == null || head.next.next == null) {
            return head;
        }
        // 2.辅助指针
        HeroNode cur = head.next;
        HeroNode next = null;   // 临时变量
        HeroNode reverse = new HeroNode(0,"","");
        // 3.指针移动，将cur中的变量放入reverse
        while (cur != null) {
            next = cur.next;
            cur.next = reverse.next;
            reverse.next = cur;
            cur = next;
        }
        head.next = reverse.next;
        return reverse;
    }

    /**
     * 面试题2：得到单链表的倒数第n个节点
     * @param n -> k
     * @return 节点
     */
    public HeroNode getLastOrder(int n) {
        int size = size();
        if (n <= 0 || n > size) {
            return new HeroNode(0,"","");
        }
        // 获取第size-n个节点
        HeroNode cur = head.next;
        for (int i = 0; i < size - n; i++) {
            cur = cur.next;
        }
        cur.next = null;
        return cur;
    }

    /**
     * 面试题3：逆序打印链表，不可以破坏原先结构
     */
    public static void listByOrder(HeroNode node) {
        // 方式一：借助栈结构来实现
        if (node.next == null) {
            return;
        }
        HeroNode cur = node.next;
        Stack<HeroNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
        // 方式二：递归实现
        // TODO: 2022/10/25 待补充 
    }

    public HeroNode getHead() {
        return head;
    }

    public void updateNode(HeroNode node) {
        // 1.找到待修改节点
        HeroNode temp = head;
        int no = node.no;
        boolean existFlag = false;
        while (true) {
            if (temp.next == null){
                break;
            }
            if (no == temp.next.no) {
                existFlag = true;
                temp.next.name = node.name;
                temp.next.nickName = node.nickName;
                break;
            }
            temp = temp.next;
        }
        // 2.不存在
        if (!existFlag) {
            System.out.printf("排行为%d的英雄不存在\n",no);
        }
    }

    public void deleteNode(HeroNode node) {
        deleteNodeByNo(node.no);
    }

    public void deleteNodeByNo(int no) {
        // 1.找到待删除节点
        HeroNode temp = head;
        boolean existFlag = false;
        while (true) {
            if (temp.next == null){
                break;
            }
            if (no == temp.next.no) {
                existFlag = true;
                break;
            }
            temp = temp.next;
        }
        // 2.如果存在，作删除
        if (existFlag) {
            temp.next = temp.next.next;
        }else {
            System.out.printf("排行为%d的英雄不存在\n",no);
        }
    }

    /**
     * 实现顺序插入：按照no排序，且no相同时不做插入
     * @param node 需要按no排序的节点
     */
    public void addByNo(HeroNode node) {
        // 1.找到添加位置
        int no = node.no;
        HeroNode temp = head;
        while (temp.next != null && no >= temp.next.no){
            if (no == temp.next.no) {
                // 提示并返回
                System.out.println("当前英雄" + node.toString() + "的排行已存在，请重新选择英雄");
                return;
            }
            temp = temp.next;
        }
        // 2.挂node
        node.next = temp.next;
        temp.next = node;
    }

    public void add(HeroNode node) {
        // 找到尾节点，插入到next中
        HeroNode temp = this.head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    public void list() {
        HeroNode temp = this.head;
        if (head.next == null) {
            System.out.println("HeroNode{ }");
        }
        while (temp.next != null){
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

    public int size() {
        int count = 0;
        HeroNode temp = this.head;
        while (temp.next != null){
            count++;
            temp = temp.next;
        }
        return count;
    }
}

/**
 * 节点
 */
class HeroNode {
    int no;
    String name;
    String nickName;
    HeroNode next;  // 尾节点

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
